#include "Union_Find_Set.hpp"

Union_Find_Set::Union_Find_Set(vector<vector<int>> mat)
{
    this->G = mat;
    this->num_node = mat.size();
    for (size_t i = 0; i < num_node; i++)
    {
        node x;
        x.index = i;
        this->forest.push_back(x);
    }
}

void Union_Find_Set::Link(node *x, node *y){
    if(x->rank > y->rank){
        y->p = x;
    }
    else{
        x->p = y;
        if(x->rank == y->rank){
            y->rank = y->rank + 1;
        }
    }
}

node* Union_Find_Set::Find_Set(node *x){
    if(x != x->p)
        x->p = Find_Set(x->p);
    return x->p;
}

void Union_Find_Set::Union(node *x, node *y){
    Link(Find_Set(x), Find_Set(y));
}

void Union_Find_Set::Make_Set(node *x){
    x->p = x;
    x->rank = 0;
}

void Union_Find_Set::Connected_Components(){
    for (size_t i = 0; i < this->num_node; i++)
    {
        this->Make_Set(&(this->forest[i]));
    }
    for (size_t i = 0; i < this->num_node; i++)
    {
        for (size_t j = 0; j < this->num_node; j++)
        {
            if (this->G[i][j] == 1)
            {
                this->Union(&this->forest[i], &this->forest[j]);
            }
        }
    }
}

bool Union_Find_Set::Same_Component(node *u, node *v){
    if(this->Find_Set(u) == this->Find_Set(v))
        return true;
    else return false;
}

int Union_Find_Set::get_union_num(){
    int num = 0;
    for (size_t i = 0; i < this->num_node; i++)
    {
        if(&(this->forest[i]) == this->forest[i].p) num ++;
    }
    return num;
}

void Union_Find_Set::run(){
    time_t begin, end;
    int union_num;
    begin = clock();
    for (size_t i = 0; i < 10000; i++)
    {
        this->Connected_Components();
        union_num = this->get_union_num();
    }
    end = clock();
    
    cout << union_num << endl << endl;
    cout << end - begin << endl << endl;
}